A variety of media are used to store digital data such as music content and image data. Examples include magnetic disks, optical discs, and magneto-optical disks. Among such recording media, memory cards that use semiconductor memories including flash ROMs as their recording elements are compact, and thus have become rapidly widespread mainly in compact portable devices, such as digital still cameras and mobile telephone terminals. In particular, semiconductor memories, which have conventionally been used as removable media like memory cards, have recently found application as built-in memories. For example, semiconductor memories, such as flash ROMs, are built in devices and used in place of hard disks.
A memory card and a built-in memory mainly use a semiconductor device called a NAND-type flash memory, which is a recording element on which recorded data can be erased and new data can be recorded. Like a conventional hard disk, the NAND-type flash memory can be used to form an information recording device that is rewritable a plurality of number of times.
A conventional way to manage data stored in a memory card or a built-in memory uses a file system. Data managed using a file system can be shared as files between a plurality of devices that can interpret the same file system. Such file system management enables a user to easily refer to or copy his or her stored data on a plurality of devices.
A file system that has conventionally achieved most widespread use is a file allocation table (FAT) file system. The FAT file system manages areas in a unified manner using a file allocation table (FAT). With its simple structure and easy implementation, the FAT file system is used in many recording media, such as flexible disks, hard disks of personal computers, and memory cards.
FIG. 2 shows the structure of the FAT file system.
The FAT file system can be of one of a plurality of types: FAT12, FAT16, and FAT32, which differ from one another in the bit width of the management unit used in their file allocation table. The FAT file system of any of these types uses substantially the same method for managing areas using the file allocation table. In this example, the FAT16 file system will be described.
As shown in FIG. 2, at the beginning of the logical address space is a file system management information area 301, which stores management information for the file system, such as information indicating the unit of area allocation and the size of areas that are managed by the file system.
The file system management information area 301 stores a plurality of sets of management information: a master boot record (MBR) partition table 303, a partition boot sector 304, FATs (305 and 306), and a root directory entry 307, each of which stores information required to manage a user data area 302.
The MBR partition table 303 stores information used to manage areas of the logical address space managed by the file system by dividing the logical address space into a plurality of areas called partitions.
The partition boot sector 304 stores information about management within each partition, such as information about the unit of area management within the partition.
The FATs (305 and 306) each stores information about the storage position of file data. The FAT file system usually has two FATs (305 and 306) each storing the same information. Even if one FAT (305 or 306) is corrupted, the duplicated feature of the FAT file system enables access to files by using the other FAT (305 or 306).
The root directory entry 307 stores information about files and directories (directory entries) that are immediately below the root directory.
The FAT file system further includes the user data area 302, which is preceded by the file system management information area 301. The user data area 302 stores main data stored in a file and the like.
The user data area 302 is managed in units of divided areas called clusters, each of which has a size of 512 bytes to tens of kilobytes. Each cluster stores data stored in a file. A file storing a large amount of data uses a plurality of clusters to store the data. The FATs (305 and 306) store link information that is used to manage links between such clusters.
Also, a part of the user data area 302 is used to store information about files and sub-directories (directory entries) immediately below the root directory.
FIG. 3 shows the structure of a directory entry of the FAT16 file system.
A directory entry 308, which has 32 bytes, is allocated to each file or each directory, and stores information associated with the file or the directory. More specifically, information representing the 32-byte directory entry 308 is newly generated every time when a file or a directory is added, and is stored into the area of the root directory entry 307 or into the user data area 302.
The first eight-byte of the directory entry 308 stores a file name or a directory name.
The following three-byte stores an extension.
The following one-byte stores attribute information, such as a flag indicating a type either being a file or a directory, and a flag indicating whether the file or the directory is read-only.
The directory entry 308 may further store information about the last update time and date of the file or the directory, a first cluster number indicating the position of a first cluster among a plurality of clusters storing the file data or the directory data, and a file size indicating the number of bytes of the file.
As described above, the directory entry 308 only stores information indicating the position of the first single cluster storing the file data or the directory data. The positions of data stored in the second and subsequent clusters are managed by the FATs (305 and 306) when the file data or the directory data is larger than the size of one cluster.
FIG. 4 shows the structure of the FAT (305, 306) used in the FAT16 file system.
In the FAT16 file system, the FAT (305, 306) manages 2-byte (16-bit) information as a single FAT entry. A single FAT entry indicates the status of its corresponding single cluster. More specifically, when the user data area 302 includes M clusters, the FAT includes M FAT entries. In this case, the FAT (305, 306) has a size of about 2*M bytes. The first two FAT entries of the FAT store, as a signature, fixed values (0xF8FF, 0xFFFF) indicating the beginning of the FAT. The fourth and fifth bytes of the FAT (305, 306) store an FAT entry corresponding to the first cluster included in the user data area 302. When the four-byte signature stored at the beginning of the FAT is assumed to be the 0-th and 1st FAT entries, the fourth and fifth bytes are the two bytes storing the second FAT entry. As a result, a cluster number of 2 is assigned to the first cluster included in the user data area 302 for convenience. The FAT includes no clusters with cluster numbers of 0 or 1.
Each FAT entry further indicates the status of the corresponding cluster (occupied, unoccupied, or defective) and a cluster number of a linked cluster. In FIG. 4, for example, an FAT entry with an assigned cluster number of 2 is set as 0x0003 (“3” when expressed as a decimal number), indicating that data subsequent to the data stored in the cluster with the cluster number of 2 is stored in a cluster with a cluster number of 3. In the same manner, an FAT entry with an assigned cluster number of 3 is set as 0x0004 (“4” when expressed as a decimal number), indicating that data subsequent to the data stored in the cluster with the cluster number of 3 is stored in a cluster with a cluster number of 4. An FAT entry with an assigned cluster number of 6 is set as 0xFFFF, indicating that no cluster is linked to this cluster, and this cluster is the end of the link. In the example shown in FIG. 4, the file data is stored over a plurality of clusters in the order of the cluster numbers of 2, 3, 4, 5, and 6.
Also, an FAT entry with an assigned cluster number of 7 is set as 0x0000, indicating that the corresponding cluster is not used and is in an unoccupied state.
An FAT entry with an assigned cluster number of (M+1) is set as 0xFFF7, indicating that the corresponding cluster is in a defective state, or that the corresponding cluster is for example physically damaged and data cannot be recorded into this cluster.
To sum up, the three FAT entry values 0x0000, 0xFFFF, and 0xFFF7 have different distinct meanings. The FAT entry values from 0x0002 to 0xFFF6 are used as cluster numbers of linked clusters. The other values, that is, the values 0x0001 and 0xFFF8 to 0xFFFE, are reserved and are not used normally.
As described above, when file data is stored over a plurality of clusters under the FAT file system, links between the clusters are stored and managed using the values of FAT entries. To read the file data sequentially from the beginning to the end, the FAT (305, 306) is to be referred to and a cluster number of the next linked cluster is to be identified every time when the data reading position reaches a boundary between clusters.
In the same manner, when an information recording system using the FAT file system reads data at a selected position within a file through seeking, the system needs to refer to the FAT (305, 306) and identify a cluster number of a cluster storing the data to be read, and follow links of clusters corresponding to the seek size. The processing time required for such seeking will be longer as the file size increases. A file having 1 GB is assumed to be managed in units of clusters each having 16 KB. In this case, the information recording system needs to follow about 65,000 links. A relatively low-speed CPU would require a processing time of as long as several seconds for such seeking. Further, the FAT (305, 306) stores link information indicating links only in the forward direction of the file. To seek in the reverse direction of the file, the information recording system needs to seek again from the beginning of the file. This prevents seeking to be performed at a high speed.
With a conventional method that can solve this problem, information about a position of a file data storage area is stored at a position immediately following a directory entry 308 of the file (see, for example, Patent Citation 1).
With this method, the directory entry 308 of the file is arranged at the beginning position of a selected cluster included in a directory area, and erased directory entries are arranged in all the other areas of the selected cluster.
Further, a plurality of pieces of logical block addressing (LBA) access information indicating start positions and end positions of areas storing the file data are stored into the erased directory entries.
The LBA access information allows seeking in a file to be performed simply by referring to the LBA access information, without requiring to refer to the FAT. This enables the seeking to be performed at a higher speed.
However, this method uses the erased directory entries to store the LBA access information. When a file or a directory is created by a device that interprets only the conventional FAT file system that is not designed to process the LBA access information, the device may erroneously use an erased directory entry storing the LBA access information and corrupt the LBA access information.
The FAT file system uses the directory entry 308 having the structure shown in FIG. 3, in which a reserved field is actually used to store, for example, information about a timestamp. In this case, the directory entry 308 lacks a sufficient amount of reserved field. As a result, the FAT file system lacks extensibility. A conventional method that can solve this problem uses an extensible file system format (see, for example, Patent Citation 2).
With this conventional method, the first 1-byte of each directory entry is used as a “type” field, which stores the type of the directory entry. This field is used to define the directory entry type, such as a primary directory entry or a second directory entry, and increases the extensibility of the file system.
The above two techniques may be combined. More specifically, the type of the directory entry may define a special directory entry storing information about a position of a file data storage area, which may then be stored as additional information of the directory entry for the file. This structure prevents a conventional device that cannot interpret the special directory entry from corrupting the information indicating a position of a file data storage area.
In this case, a plurality of directory entries are allocated to a single file. This structure further requires a mechanism for ensuring consistency between directory entries and enhancing the reliability of the directory entries. One such mechanism may use a cyclic shift checksum, which is implemented, for example, as a “sum” command in a Unix (registered trademark) operating system.
FIG. 5 is a flowchart showing a process for calculating a cyclic shift checksum.
The cyclic shift checksum is calculated not only by simply adding calculation target data but also by cyclically shifting the value by a single bit every time when adding data. Such cyclic shift allows an error to be detected even when the sequence of the calculation target data is changed, thereby enhances reliability.
The cyclic shift checksum is calculated using all directory entry areas allocated to a single file as the calculation target data, and the calculated cyclic shift checksum is then stored into a specific field of each directory entry. This allows corruption of any directory entry to be detected, thereby enhances reliability.    Patent Citation 1: Japanese Unexamined Patent Publication No. 2006-178632    Patent Citation 2: Japanese Unexamined Patent Publication No. 2006-172485